A need for data compression arises in many types of systems which process graphic images. Such systems include digital facsimile machines, electronic mail systems, digital copiers, graphic work stations and storage and retrieval systems. Thus the problem of encoding data representing a graphic image in order to accomplish compression arises in many environments.
A digital facsimile system, in which the preferred embodiment of the present invention is implemented, is an information communication machine by which picture information is transmitted from one location to another location over a communication link such as a telephone line. Typically, in facsimile systems, a scanner generates a facsimile of a graphic image by scanning the original image, such as on a document, on a line-by-line basis, each line including a large number of picture elements. The generated facsimile is then encoded by either a one-dimensional or a two-dimensional coding scheme to compress the image data to reduce the bandwidth or transmission time required for communicating the facsimile. The compressed data is then transmitted over communication links to remote facsimile machines. The remote facsimile machine decodes the compressed data to regenerate the facsimile and reproduces the original graphic image.
One-dimensional coding schemes are based upon the correlation of picture elements along a given scan line in the horizontal direction, whereas two-dimensional coding schemes are based upon a vertical correlation between successive scan lines in addition to the horizontal correlation. Both one-dimensional and two-dimensional schemes have been standardized by the International Telegraph and Telephone Consultative Committee (CCITT). The CCITT standards set forth in Recommendations T.4 and T.6 define a standard coding scheme for Group 3 and Group 4 facsimile apparatus. The recommendations of the CCITT have established compatibility among manufacturers of facsimile equipment for communication of encoded facsimile data.
The CCITT Group 3 apparatus uses a modified Huffman (MH) coding scheme for one-dimensional coding and a modified Relative Element Address Designate (MR) coding scheme for two-dimensional coding. The CCITT Group 4 apparatus uses a modified MR (MMR) coding scheme for two-dimensional coding. The one-dimensional MH coding method uses Huffman codes for the run length of black or white picture elements (PELs).
The two-dimensional coding method encodes the picture by using not only the current line information but also the previous line information. This method is a line-by-line coding method in which the position of each changing PEL on the coding line is coded with respect to the position of a corresponding reference PEL situated on either the coding line or a reference line. Based on the relative position of changing PELs, three coding modes are defined in the CCITT standards: Pass mode, Vertical mode and Horizontal mode.
For the two-dimensional coding, the CCITT standard identifies five color changing elements, a0, a1, a2, b1 and b2, which are elements whose "color" differs from that of the previous adjacent element along the same scan line. The a0 is the reference or starting element on the coding line. At the start of the coding line a0 is set on an imaginary white changing element situated just before the first element on the line. During the coding of the coding line, the position of a0 is defined by the previous coding mode. The al is the next changing element to the right of a0 on the coding line. The a2 is the next changing element to the right of a1 on the coding line. The b1 is the first changing element on the reference line to the right of a0 and of the opposite color to a0. The b2 is the next changing element to the right of b1 on the reference line.
The pass mode is identified when the position of b2 lies to the left of a1. When this mode has been coded, the picture element just under b2 is regarded as the new starting picture element a0 for the next coding. However, the state where b2 occurs just above a1 is not considered as a pass mode. If it is not a pass mode and the relative distance of a1b1 is less than or equal to three, then a vertical mode is identified. The relative distance a1b1 can take on one of seven values V(0), VR(1), VR(2), VR(3), VL(1), VL(2), and VL(3), each of which is represented by a separate code word. After the vertical mode has been coded, position a1 is regarded as the new starting picture element a0 for the next coding. Also, if it is not a pass mode and the relative distance of a1b1 is greater than three, then a horizontal mode is identified. When this mode is identified, both the run-lengths a0a1 and a1a2 are coded using the code words H+M(a0a1)+M(a1a2), where M(X) is a standard run-length code. After the horizontal mode has been coded, position a2 is regarded as the new starting picture element a0 for the next coding.